
/*
5. [最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/description/)
辛泽豪
*/


class Solution {
public:
    // 函数定义，用于找到字符串s中最长的回文子串
    string longestPalindrome(string s) {
        int n = s.size();  // 获取输入字符串s的长度
        // 创建一个二维动态规划数组dp，用于存储子串是否是回文的信息
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        
        // 单个字符一定是回文，因此将dp[i][i]设置为true
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 记录最长回文子串的起始位置
        int begin = 0;
        // 初始化最长回文子串长度为1（即单个字符）
        int maxLen = 1;  
        
        // 从后往前遍历所有可能的左边界left
        for (int left = n - 1; left >= 0; left--) {
            // 对于每一个left，检查所有可能的右边界right
            for (int right = left + 1; right < n; right++) {
                // 当子串长度为2时
                if (right - left == 1) {
                    // 如果左右两边字符相同，则该子串为回文
                    if (s[left] == s[right]) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = false;
                    }
                } else {  // 子串长度大于2的情况
                    // 如果左右两端字符相同，并且去掉两端之后的子串也是回文，则该子串为回文
                    if (s[left] == s[right] && dp[left + 1][right - 1] == true) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = false;
                    }
                }
                
                // 如果发现了一个新的更长的回文子串，更新begin和maxLen
                if (dp[left][right] && right - left + 1 > maxLen) {
                    begin = left;
                    maxLen = right - left + 1;
                }
            }
        }
        // 返回最长回文子串
        return s.substr(begin, maxLen);
    }
};